package search

var count int

// 快排
func quickSort(nums []int) int {
	count = 0
	sort(nums, 0, len(nums)-1)
	return count
}

func sort(nums []int, left int, right int) {
	if left < right {
		partitionIndex := partition(nums, left, right)
		sort(nums, left, partitionIndex-1)
		sort(nums, partitionIndex+1, right)
	}
}

func partition(nums []int, left int, right int) int {
	pivot := left
	index := pivot + 1
	for i := index; i <= right; i++ {
		count++
		if nums[i] < nums[pivot] {
			swap(nums, i, index)
			index++
		}
	}
	swap(nums, pivot, index-1)
	return index - 1
}

func swap(nums []int, i int, j int) {
	temp := nums[i]
	nums[i] = nums[j]
	nums[j] = temp
}
